package Demo83;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 图像渲染
 * https://leetcode.cn/problems/flood-fill/description/
 */
class Solution {
    int[] dx = new int[] {0,0,1,-1};
    int[] dy = new int[] {1,-1,0,0};
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int prve = image[sr][sc]; // 记录原始值
        if(prve == color) return image; // 处理边界情况
        int m = image.length, n = image[0].length;
        // 创建队列
        Queue<int[]> q = new LinkedList<>();
        // 入队
        q.add(new int[] {sr,sc});
        // 层序遍历
        while(!q.isEmpty()) {
            int[] t = q.poll();
            int a = t[0], b = t[1];
            image[a][b] = color;
            for(int i = 0; i < 4;i++) {
                int x = a + dx[i], y = b + dy[i];
                if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prve) {
                    q.add(new int[] {x,y});
                }
            }
        }
        return image;
    }
}